import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LEET516 {
    /*
    LCR 019. 验证回文串 II
     */
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length()-1;
        while (left < right){
            char c1 = s.charAt(left);
            char c2 = s.charAt(right);
            if (c1 == c2){
                left++;
                right--;
            }else{
                //不相等了，那么就删除一个字符，再判断
               return validPalindrome(s,left+1,right) || validPalindrome(s,left,right-1);
            }
        }
        return true;
    }

    private boolean validPalindrome(String s, int left, int right) {
        while (left < right) {
            char c1 = s.charAt(left);
            char c2 = s.charAt(right);
            if (c1 == c2) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }
/*
LCR 072. x 的平方根
 */
    public int mySqrt(int x) {
        int l = 0;
        int r = x;
        int ans = -1;
        while (l <= r){
            int mid = l+(r-l)/2;
            if ((long)mid*mid <= x){
                ans = mid;
                l = mid+1;
            }else {
                r = mid-1;
            }
        }
        return ans;
    }
/*
LCR 006. 两数之和 II - 输入有序数组
 */
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int l = i+1;
            int r = numbers.length-1;
            while (l <= r){
                int mid = l+(r-l)/2;
                if (numbers[mid] == target - numbers[i]){
                    return new int[]{i,mid};
                }else if (numbers[mid] > target - numbers[i]){
                    r = mid-1;
                }else {
                    l = mid+1;
                }
            }
        }
        return new int[]{-1,-1};
    }


/*
LCR 002. 二进制求和
 */
    public String addBinary(String a, String b) {
        int alen = a.length()-1;
        int blen = b.length()-1;
        StringBuffer stringBuffer = new StringBuffer();
        int maxLen = Math.max(alen,blen);
        int carry = 0;
        for (int i = 0; i <= maxLen; i++) {
            carry += i <= alen ? (a.charAt(alen - i)-'0') : 0;
            carry += i <= blen ? (b.charAt(blen - i)-'0') : 0;
            stringBuffer.append((char)(carry%2+'0'));
            carry /= 2;
        }
        if (carry > 0) {
            stringBuffer.append('1');
        }
        return stringBuffer.reverse().toString();


    }

    public static void main(String[] args) {
        StringBuffer stringBuffer = new StringBuffer();
        stringBuffer.lastIndexOf("1");
        stringBuffer.lastIndexOf("2");
        System.out.println(stringBuffer.toString());
    }

    /*
    LCR 003. 比特位计数
     */
    public int[] countBits(int n) {
        int[] ans = new int[n+1];
        for (int i = 0; i <= n; i++) {
            ans[i] = countBit(i);

        }
        return ans;
    }

    private int countBit(int i) {
        int count = 0;
        while (i > 0){
            i &= (i-1);
            count++;
        }
        return count;
    }

/*
LCR 001. 两数相除
 */
    public int divide(int a, int b) {
        int flag = 1;
        if (b < 0){
            flag = -1;
        }
        int left = 1;
        int right = a;
        if (a < 0){
            left = a;
            right = 0;
        }

        while (left <= right){
            int mid = left+(right-left)/2;
            if (Math.abs(mid*b)== a){
                return mid*flag;
            }else if (Math.abs(mid*b) > a){
                right = mid-1;
            }else {
                left = mid+1;
            }
        }
        return right*flag;
    }
}
